package _07_abstractGraph;

import _02_seqList.SeqList;
import _04_seqQueue.CirSeqQueue;
import _04_seqQueue.Queue;

public abstract class AbstractGraph<T> implements Graph<T> {
    
    // 最大权值（表示无穷大）
    protected static final int  MAX_WEIGHT = 0x0000fffff;
    // 顶点顺序表，存储图的顶点集合
    protected SeqList<T> vertexlist;
    
    // 构造空图，顶点数为0
    public AbstractGraph() {
        // 构造空顺序表，默认容量
        this.vertexlist = new SeqList<T>();
    }
    
    // 返回顶点个数
    public int vertexCount() {
        // 返回顶点顺序表的元素的个数
        return this.vertexlist.size();
    }
    
    // 返回图的顶点集合的描述字符串
    public String toString() {
        return "顶点集合：" + this.vertexlist.toString() + "\n";
    }
    
    // 返回顶点vi元素；若i越界，则返回null
    public T get(int i) {
        return this.vertexlist.get(i);
    }
    
    // 设置顶点vi元素为x
    public void set(int i, T x) {
        // 若i越界，则抛出异常
        this.vertexlist.set(i, x);
    }
    
    // 查找并返回首个与key相等的顶点序号
    public int search(T key) {
        return this.vertexlist.search(key);
    }
    
    // 没有实现Graph<T>接口声明的抽象方法insert(T)、remove(int)、weight(int, int)
    // 查找并删除首个与key相等的顶点及其相关联的边
    public T remove(T key) {
        // 删除顶点vi及其关联的边，抽象方法，待子类实现
        return this.remove(this.search(key));
    }
    // 返回vi再vj后的后继邻接顶点序号
    protected abstract int next(int i, int j);
    
    // 返回<vi, vj>边的权值
    public abstract int weight(int i, int j);
    
    // 图的深度优先遍历，从顶点vi出发
    public void DFSTraverse(int i) {
        if (i < 0 || i >= this.vertexCount()) {
            return;
        }
        // 访问标记数组，元素初值为false
        boolean[] visited = new boolean[this.vertexCount()];
        int j = i;
        while (true) {
            // 若顶点i未被访问
            if (visited[j] == false) {
                System.out.print("{");
                depthfs(j, visited);
                System.out.print("}");
            }
            j = (j + 1) % this.vertexCount();
            if (j == i) {
                break;
            }
        }
        System.out.println();
    }
    // 从顶点vi出发的一次深度优先搜索，遍历一个连通分量；visited[]指定访问标记，引用类型，递归算法
    private void depthfs(int i, boolean[] visited) {
        // TODO Auto-generated method stub
        System.out.print(this.get(i) + " ");
        visited[i] = true;
        // 以下循环j依次获得vi的所有邻接顶点序号。next(i, j)返回vi在vj后的后继邻接顶点序号；
        // 若j = -1，则返回vi的第0个邻接顶点序号；若不存在后继邻接顶点，则返回-1
        for (int j = next(i, -1); j != -1; j = next(i, j)) {
            if (visited[j] == false) {
                depthfs(j, visited);
            }
        }
    }
    
    // 图的广度优先遍历，从顶点vj出发
    public void BFSTraverse(int i) {
        if (i < 0 || i >= this.vertexCount()) {
            return;
        }
        Queue<Integer> queue = new CirSeqQueue<Integer>(this.vertexCount() - 1);
        boolean[] visited = new boolean[this.vertexCount()];
        queue.add(i);
        int j = i;
        while (true) {
            // System.out.print(j); // 过程监控
            if (visited[j] == false) {
                System.out.print("{");
                breadthfs(j, visited, queue);
                System.out.print("}");
            }
            j = (j + 1) % this.vertexCount();
            if (j == i) {
                break;
            }
        }
        System.out.println();
    }
    private void breadthfs(int i, boolean[] visited, Queue<Integer> queue) {
        // TODO Auto-generated method stub
        System.out.print(this.get(i) + " ");
        visited[i] = true;
        queue.add(i);
        while (!queue.isEmpty()) {
            i = queue.poll();
            for (int j = next(i, -1); j != -1; j = next(i, j)) {
                if (visited[j] == false) {
                    System.out.print(this.get(j) + " ");
                    visited[j] = true;
                    queue.add(j);
                }
            }
        }
    }

    // 构造带权无向图的最小生成树，Prim算法
    public void minSpanTree() {
        
    }
    // 求带权图顶点vi的单源最短路径，Dijkstra算法
    public void shortestPath(int i) {
        
    }
    // 求带权图没对顶点间的最短路径及长度，Floyd算法
    public void shortestPath() {
        
    }

}
